package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/minimum-genetic-mutation/">433. 最小基因变化</a>
 */
public class Problem443 {
    private static class Solution {
        public int minMutation(String start, String end, String[] bank) {
            if (start.equals(end)) {
                return 0;
            }
            Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
            if (!bankSet.contains(end)) {
                return -1;
            }
            final char[] CHARS = new char[]{'A', 'C', 'G', 'T'};
            int steps = 0;
            Set<String> visited = new HashSet<>();
            Queue<String> mutated = new ArrayDeque<>();
            mutated.offer(start);
            while (!mutated.isEmpty()) {
                steps++;
                int size = mutated.size();
                for (int i = 0; i < size; i++) {
                    String cur = mutated.poll();
                    for (int j = 0; j < 8; j++) {
                        for (char aChar : CHARS) {
                            if (aChar != cur.charAt(j)) {
                                StringBuilder sb = new StringBuilder(cur);
                                sb.setCharAt(j, aChar);
                                String next = sb.toString();
                                if (next.equals(end)) {
                                    return steps;
                                }
                                if (!visited.contains(next) && bankSet.contains(next)) {
                                    visited.add(next);
                                    mutated.offer(next);
                                }
                            }
                        }
                    }
                }
            }
            return -1;
        }
        //TODO：
        // 1. 邻接表预处理方案
        // 2. 双向BFS
        // 3. A*算法

    }

    public static void main(String[] args) {
        System.out.println(new Solution().minMutation("AACCTTGG", "AATTCCGG", new String[]{"AATTCCGG", "AACCTGGG", "AACCCCGG", "AACCTACC"}));
    }
}